package B刷题.A栈和队列;

import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：最大值减去最小值小于或等于num的子数组数量
 * @date 2022/12/8 11:18
 */
public class Code11_GetNum {

    /**
     * 思路：
     * 全部子数组数量=以各个位置为头的子数组数量之和；
     * 各个位置为头的子数组数量=找到以该头为起点满足最大值-最小值小于等于num最大范围内的每一个子数组；
     * 求范围最大值、最小值，而且不断向右移动，想到滑动窗口；
     * 注意：
     * 1.while里面的条件可以拆开写，防止过长不好理解且容易出错，里面加上break条件；
     * 2.栈、队列，查看、弹出元素之前一定要判空；
     */
    public static int getNum(int[] arr, int num) {
        int result = 0;
        if (arr == null || arr.length == 0 || num < 0) {
            return result;
        }
        LinkedList<Integer> maxQueue = new LinkedList<>();
        LinkedList<Integer> minQueue = new LinkedList<>();
        // 当前来到的位置
        Integer cur = 0;
        for (int i = 0; i < arr.length; i++) {
            while (cur < arr.length) {
                // 当前值与最大值、最小值的差距大于num，则停止
                if ((!maxQueue.isEmpty() && arr[maxQueue.peek()] - arr[cur] > num) || (!minQueue.isEmpty() && arr[cur] - arr[minQueue.peek()] > num)) {
                    break;
                }
                // 进大队列：只要末尾元素小于当前元素，弹出
                while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] < arr[cur]) {
                    maxQueue.pollLast();
                }
                maxQueue.add(cur);
                // 进小队列
                while (!minQueue.isEmpty() && arr[maxQueue.peekLast()] > arr[cur]) {
                    minQueue.pollLast();
                }
                minQueue.add(cur);
                cur++;
            }
            // 以i开头，最大值-最小值<=num的最右边+1的一个位置就是cur
            result = result + (cur - i);
            // 当前元素弹出大队列、小队列
            if (i == maxQueue.peek()) {
                maxQueue.pollFirst();
            }
            if (i == minQueue.peek()) {
                minQueue.pollFirst();
            }
        }
        return result;
    }

}
